package org.example.sward.tooffer;

import java.util.Stack;

/**
 * <p>
 * Description:TODO 详细描述
 * <p>
 * Copyright: 天津联想协同科技有限公司
 * <p>
 *
 * @author anlu
 * @date 2022/3/14 14:14
 */
public class Offer33 {
    public static void main(String[] args) {
        Offer33 offer33 = new Offer33();
        int[] nums = {1,3,2,6,5};
        boolean result = offer33.verifyPostorder(nums);
        System.out.println(result);

    }

    /**
     * 后续遍历
     * @param postorder
     * @return
     */
    public boolean verifyPostorder(int[] postorder) {
        return recur(postorder,0,postorder.length - 1);
    }

    /**
     * 递归查找
     * @param postorder
     * @param i 左子节点
     * @param j 根节点
     * @author: anlu
     * @time: 2022/3/14
     */
    private boolean recur(int[] postorder, int i, int j) {
        //递归的终止条件
        if(i >= j){
            return true;
        }
        int p = i;
        while (postorder[p] < postorder[j]){
            p++;
        }
        //设置右子树
        int m = p;
        while (postorder[p] > postorder[j]){
            //此时p就移动到根节点
            p++;
        }

        return p == j && recur(postorder,i,m - 1) && recur(postorder,m, j - 1);

    }

    public void solution2(int[] postorder){
        Stack<Integer> stack = new Stack<>();

    }


}
